#include <stdio.h>
#include <stdlib.h>

struct Node {
  int x; // data
  struct Node *s; // next
} *head = NULL;

typedef struct Node SLLNode; // *_*

void printLL(struct Node* h) {
  struct Node *ptr = h;
  // if (ptr) { // recursive
  //   printf("%d\n", h->x);
  //   printLL(ptr->s);
  // } 
  while(h) { // iterative
    printf("%d --> ", h->x);
    h = h->s;
  } 
  printf("\n");
}

void printReverseLL(struct Node* h) {
  struct Node *ptr = h;
  if (ptr) { // recursive
    printReverseLL(ptr->s);
    printf("%d\n", h->x);
  } 
}

SLLNode* insertAtBeginning(SLLNode *head, int val) {
  SLLNode *newNode = (SLLNode*) malloc(sizeof(SLLNode));
  newNode->x = val;
  newNode->s = head;
  return newNode;
}

SLLNode* insertAtEnding(SLLNode *head, int val) {
  SLLNode *newNode = (SLLNode*) malloc(sizeof(SLLNode));
  newNode->x = val;
  newNode->s = NULL;
  if (head == NULL)
    return newNode;
  SLLNode* ptr = head;
  while (ptr->s)
    ptr = ptr->s;
  ptr->s = newNode;
  return head;
}

SLLNode* insertAtPosition(SLLNode *head, int pos, int val) {
  if (pos == 1)
    return insertAtBeginning(head, val);
  SLLNode* ptr = head;
  SLLNode* newNode = (SLLNode*) malloc(sizeof(SLLNode));
  newNode->x = val;
  for (int i = 0; i < pos - 2; i++)
  {
    if (!ptr->s) {
      ptr->s = newNode;
      return head;
    }
    ptr = ptr->s;
  }
  newNode->s = ptr->s;
  ptr->s = newNode;
  return head;
}

void createLL() { // demo [100, 200, 300]
  head = (struct Node *) malloc(sizeof(struct Node));
  head->x = 100;
  head->s = (struct Node *) malloc(sizeof(struct Node));
  head->s->x = 200;
  head->s->s = (struct Node *) malloc(sizeof(struct Node));
  head->s->s->x = 300;
  head->s->s->s = NULL;
}

int main() {
  createLL();
  // printReverseLL(head);
  printLL(head);
  head = insertAtBeginning(head, 400);
  head = insertAtBeginning(head, 500);

  printLL(head);
  head = insertAtEnding(head, 600);
  head = insertAtEnding(head, 700);

  printLL(head);
  head = insertAtPosition(head, 7, 800);
  printLL(head);
}